#include <iostream>


// //冒泡排序
// // void BubbleSort(int *a, int size)
// // {
// //     for(int i = 0; i < size - 1; i++)
// //     {
// //         for(int j = 0; j < size - i - 1; j++)
// //         {
// //             if(a[j] > a[j + 1])
// //             {
// //                 int temp = a[j];
// //                 a[j] = a[j + 1];
// //                 a[j + 1] = temp;
// //             }
// //         }
// //     }    
// // }

// //优化后
// void BubbleSort(int *a, int size)
// {
//     for(int i = 0; i < size - 1; i++)
//     {
//         int flag = 0;
//         for(int j = 0; j < size - i - 1; j++)
//         {
//             if(a[j] > a[j + 1])
//             {
//                 flag = 1;
//                 int temp = a[j];
//                 a[j] = a[j + 1];
//                 a[j + 1] = temp;
//             }
//         }
//         if (flag == 0)
//         {
//             break;
//         }
//     }    
// }

//插入排序：用于已经有序的序列，插入新的数字
void InsertSort(int *a, int size)
{
    for(int i = 1; i < size; i++)//外循环，从第二个位置开始依次插入有序序列
    {
        int j = i; 
        int temp = a[i];
        for(;j > 0;j--)//从当前位置，依次往前比较
        {
            if(temp < a[j - 1])//比前面的数小，则前面的数字向后挪
            {
                a[j] = a[j - 1];
            }
            else
            {
                break;
            }
        }
        a[j] = temp;//比前面的数大，则在现有位置插入当前数值
    }
}

//选择排序：更适合在有选择的情况下进行排序，时间复杂度是n^2
void SelectSort(int* a, int size)
{
    for(int i = 0; i < size - 1; i++)//从第i个数
    {
        int min = i;//假设第i个数最小
        for(int j = i + 1; j < size; j++)
        {
            if(a[j] < a[min])
            {
                min = j;//找到比min更小的值，交换下标
            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

//双指针算法:比单指针少一半，但时间复杂度依然是n^2
void SelectSort2(int *a, int size)
{
    int left = 0;//从最左边开始走，放最小值
    int right = size - 1;//从最右边开始走，放大值
    for(;left < right;left++,right--)
    {
        int min = left;
        int max = right;
        for(int i = left; i <= right; i++)
        {
            if(a[i] < a[min])//当前比min小，交换下标
                min = i;
            if(a[i] > a[max])//当前比max大，交换下标
                max = i;
        }
        std::swap(a[left],a[min]);//最左边和min交换位置
        if(max == left)
        {
            max = min;//当最大值在最左边，则和min交换下标
        }
        std::swap(a[right],a[max]);//最右边和max交换位置
    }
    

}


//快速排序
void QuickSort(int *a, int start, int end)//要告诉左边界和右边界
{
    //递归终止条件
    if(start >= end)//越界了，直接返回
        return;
    int left = start;//左边为较小值
    int right = end;//右边为较大值
    int temp = a[left];//定义最左值为基准值
    while(left < right)
    {
        while(left < right && a[right] > temp)//左值不能等于右值，右值大于基准值
            right--;//右值指针左移
        if(left < right)//排除掉左值等于大于右的条件，右值小于基准值时
            a[left++] = a[right];//右值给左值，左值指针右移
        while(left < right && a[left] < temp)//左值小于基准值
            left++;
        if(left < right)//左值大于基准值
            a[right--] = a[left];//左值给右值，右值指针左移
    }
    a[left] = temp;//left和right相遇时，基准值给左值
    QuickSort(a,start,left-1);//对左半边进行递归
    QuickSort(a,right+1,end);//对右半边再进行递归
}

//递归思想


int main()
{
    int a[] = {2,5,1,9,3,7};

    // //插入排序
    // InsertSort(a,sizeof(a)/sizeof(a[0]));
    //选择排序
    // SelectSort(a,sizeof(a)/sizeof(a[0]));
    // SelectSort2(a,sizeof(a)/sizeof(a[0]));
    QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);//对应int end,最后一个元素的下标是size-1
    // //冒泡排序
    // BubbleSort(a,sizeof(a)/sizeof(a[0]));
    for(int i = 0; i < sizeof(a)/sizeof(a[0]);i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;

    return 0;
}